package arima;

import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.BitSet;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Vector;

import stats.MrgExpStats;

import mining.CsvReader;
import mining.ItemSetMining;

public class MrgExp extends ItemSetMining {

	public static void main(String[] args) {
//		for (int i = 0; i < 5; i++) {
			run();
//		}
	}
	
	public static void run() {
//		String location = "./datasets/mock/mock.data.6.modified";
//		String location = "./datasets/spect/SPECT.reduced.modified";
//		String location = "./datasets/syn/T.3L5.0N0.025.data";
//		String location = "./datasets/zoo/zoo.data.modified";
		String location = "./datasets/connect4/connect-4.data.modified";
//		String location = "./datasets/mushroom/agaricus-lepiota.data.modified";
//		String location = "./datasets/monk/monks.all.modified";

		MrgExp a;
//		for (int i : new int[]{3250,3006,2763,2519,2275,2031,1788,1544,1300,1057,813,569,325}) {
		for (int i : new int[]{6000}) {
			System.out.println("---------------------------");
			a = new MrgExp(location);
			long t1 = System.nanoTime();
			a.setMinRareItemsetSupport(1);
			a.setMinFreqItemsetSupport(i);
			System.out.println("support: " + i);
			a.findMinGenerators();
			long t2 = System.nanoTime();
			
			System.out.println("total time: " + (t2 - t1)/1000000);
		}
	}

	final private MrgExpStats stats = new MrgExpStats();
	
	private BufferedWriter bwZG = null;
	private BufferedWriter bwMRG = null;
	private static final boolean write = true; 
	
	public MrgExp(String filePath) {
		super(filePath);
		this.stats.className = this.getClass().getSimpleName();
		this.stats.write = write;
		this.stats.location = filePath;
	}

	/*
	 * *******************************************
	 * 
	 * 		First part of Arima Algorithm
	 * 
	 * *******************************************
	 */

	// list of unique 1-itemsets
//	public List<Integer> allItems = new ArrayList<Integer>();
//	public int[] allItems;
	// set of itemsets and their supports - note that this is INCOMPLETE - it
	// misses some non-generator frequent itemsets
//	public Map<Itemset, Integer> itemsetFreqsIncomplete = new HashMap<Itemset, Integer>();
	// set of frequent generators found during first part of ARIMA
//	public Set<Itemset> frequentGenerators = new HashSet<Itemset>();
	// set of rare generators found from first part of ARIMA
//	public Set<Itemset> minRareGenerators = new HashSet<Itemset>();
	// set of zero generators - note that these are only those generated from
	// the first part of ARIMA, and may be incomplete
//	public Set<Itemset> minZeroGeneratorsIncomplete = new HashSet<Itemset>();
	public void findMinGenerators() {
		if (write)
		{
			try
			{
				this.filename = this.filePath + "-" + this.getMinRareItemsetSupport() + "-" + this.getMinFreqItemsetSupport() + "-";
				this.bwZG = new BufferedWriter(new FileWriter(this.filename + "zg"));
				this.bwMRG = new BufferedWriter(new FileWriter(this.filename + "mrg"));
			} catch (IOException e)
			{
				e.printStackTrace();
			}
		}

		long t1 = System.nanoTime();

//		System.out.println("Running: " + this.getClass().getSimpleName());
//		System.out.println("minRareItemsetSup: " + this.getMinRareItemsetSupport() + " | minFreqItemsetSup: " + this.getMinFreqItemsetSupport());

		Vector<Integer> oneItemsetFreqs = this.countOneItemsets();

//		int[] oneItemsetFreqs = countItemSupport_BitSetRemember();
//		this.allItems = new int[this.getUniqueItemCount()];
		
//		System.out.println(allItems);

//		this.itemsetFreqsIncomplete.putAll(oneItemsetFreqs);

		// stores current level of frequent generators
		Map<BitSet, Integer> currentFrequentGenerators = generatorAndSupportTest_1itemset(oneItemsetFreqs);

		int size = 1;
		while (!currentFrequentGenerators.isEmpty()) {
//			System.out.print(".");
//			System.out.println(((List<String>)currFgs.toArray()[0]).size());

			// testing
//			for (Itemset itemset : currentFrequentGenerators.keySet()) {
//				assert (itemsetFreqsIncomplete.get(itemset) >= minimumFrequentItemsetSupport);
//			}
			Map<BitSet, Integer> candidates = this.genCandidatesFirstPart(currentFrequentGenerators, size);
			Map<BitSet, Integer> ithLayerItemSetFreqs = this.countItemsetSupport(candidates.keySet(), size + 1);
//			System.out.println(candidates.size());
			currentFrequentGenerators = this.sortGenerators(candidates,	ithLayerItemSetFreqs);
			size++;
		}
//		System.out.println();
		
//		System.out.println("iteration itemset sizes: " + this.stats.numIterationItemsets);
//		System.out.println("number if items in all itemsets: " + this.stats.numItemsetItems);
//		System.out.println("result size: " + this.stats.numItemsets);
		
		long t2 = System.nanoTime();
		this.stats.runtime = (t2-t1)/1000000;
		this.stats.iterations = size;
		
		if (write)
		{
			try
			{
				this.bwZG.close();
				this.bwMRG.close();
			} catch (IOException e)
			{
				e.printStackTrace();
			}
		}

		System.out.println(this.stats);
	}
	
	private Vector<BitSet> transactionRecord;
	/**
	 * If there are "gaps" in the naming of items, i.e. there are no items with name of "3", in
	 * any of the transactions, then the vector value at index 3 will be null.
	 */
	private Vector<Integer> countOneItemsets() {
		this.transactionRecord = new Vector<BitSet>();
		this.transactionRecord.setSize(32);
		
		Vector<Integer> itemFreqs = new Vector<Integer>();
		itemFreqs.setSize(16);
		
		int transactionCount = 0;
		int maxItemName = 0;
		for (CsvReader reader = new CsvReader(this.filePath); reader.hasNext(); ) {
			List<Integer> transaction = new ArrayList<Integer>(reader.read());
			if (this.transactionRecord.size() < transactionCount + 1)
				this.transactionRecord.setSize((int) (this.transactionRecord.size() * 2));
			this.transactionRecord.set(transactionCount, new BitSet());
			for (int item : transaction) {					// count item frequency
				this.transactionRecord.get(transactionCount).set(item);
				if (itemFreqs.size() <= item)
					itemFreqs.setSize(itemFreqs.size() * 2);
				if (itemFreqs.get(item) == null) {
					maxItemName = Math.max(maxItemName, item + 1);
					itemFreqs.set(item, 1);
				} else {
					itemFreqs.set(item, itemFreqs.get(item)+1);
				}
			}
			transactionCount++;
		}
		this.transactionRecord.setSize(transactionCount);
		itemFreqs.setSize(maxItemName);
//		transactionRecord2.trimToSize();
//		itemFreqs.trimToSize();
		
		this.transactionCount = transactionCount;

		return itemFreqs;
	}
	
	private Map<BitSet, Integer> genCandidatesFirstPart(Map<BitSet, Integer> currentFrequentGenerators, int size)
	{
		BitSet[] fGs = currentFrequentGenerators.keySet().toArray(new BitSet[currentFrequentGenerators.size()]);
		Map<BitSet, Integer> next = new HashMap<BitSet, Integer>(); 
		
		// look through all generators, and find all the items that are included in them
		// using these items, generate all resulting sets
		
		BitSet items = (BitSet) fGs[0].clone();
//		for (int i = 1; i < fGs.length && fGs[i].cardinality() < this.getUniqueItemCount(); i++) {
		for (int i = 1; i < fGs.length; i++) {
			items.or(fGs[i]);
		}
				
		for (int i = 0; i < fGs.length; i++) {
			BitSet itemset = (BitSet) fGs[i];
			for (int item = items.nextSetBit(0); item >= 0; item = items.nextSetBit(item + 1))
			{
				if (!itemset.get(item))
				{
					BitSet merged = (BitSet) itemset.clone();
					merged.set(item);
					if (!next.containsKey(merged))
					{
						int maxSubsetSupport = Integer.MIN_VALUE;
						boolean everySubsetExists = true;

						assert ((size + 1) == merged.cardinality()) : (size + 1) + " does not equal " + merged.cardinality();

						for (int item2 = merged.nextSetBit(0); item2 >= 0; item2 = merged.nextSetBit(item2 + 1))
						{
							BitSet subset = new BitSet();
							subset.or(merged);
							subset.set(item2, false);
							if (!currentFrequentGenerators.containsKey(subset)) {
								everySubsetExists = false;
								break;
							} else {
								int subsetSupport = currentFrequentGenerators.get(subset);
								maxSubsetSupport = Math.max(maxSubsetSupport, subsetSupport);
							}
						}
						merged.nextSetBit(0);

						if (everySubsetExists)
							next.put(merged, maxSubsetSupport);

					}
				}
			}
		}
		
		return next;
	}

	private Map<BitSet, Integer> countItemsetSupport(Set<BitSet> itemsets, int size) {
		Map<BitSet, Integer> supportCounts = new HashMap<BitSet, Integer>(itemsets.size());

		for (BitSet itemset : itemsets) {
			int count = 0;
			for (BitSet transaction : this.transactionRecord) {
				if (this.hasSubset_modified(transaction, itemset))
					count++;
			}
			supportCounts.put(itemset, count);
		}
//		System.out.println(Arrays.toString(counts));
		
		return supportCounts;
	}
	
//	private boolean hasSubset_modified(BitSet transaction, BitSet subset) {
////		BitSet clone = (BitSet) subset.clone();
//		BitSet clone = new BitSet();
//		clone.or(subset);
//		clone.and(transaction);
//		return clone.equals(subset);
//	}
	private boolean hasSubset_modified(BitSet transaction, BitSet subset) {
		for ( int item = subset.nextSetBit(0); item >= 0; item = subset.nextSetBit(item + 1)) {
			if (!transaction.get(item))
				return false;
		}
		return true;
	}
	
//	long numItemsets;
//	List<Long> numIterationItemsets = new ArrayList<Long>();
	long iterationItemsetCount;
//	long numItemsetItems;
	
	// put 1-itemsets into fgs or rgs or neither
	/**
	 * Sort the one-itemsets as either frequent generator, rare generator or neither.
	 * The resulting Map only contains BitSet keys that have support values of at least 1. 
	 */
	private Map<BitSet, Integer> generatorAndSupportTest_1itemset(Vector<Integer> oneItemsetFreqs) {
		this.iterationItemsetCount = 0;
		Map<BitSet, Integer> currentFrequentGenerators = new HashMap<BitSet, Integer>();
		for (int item = 0; item < oneItemsetFreqs.size(); item++) {
			BitSet itemset = new BitSet();
			itemset.set(item);
			int sup = 0;
			if (oneItemsetFreqs.get(item) != null)
			{
				sup = oneItemsetFreqs.get(item);
				this.itemCount++;
			}
			// check if support is less than empty set (i.e. is a generator)
			if (sup != getTransactionCount())
			{
				// System.out.println(entry.getKey() + " is a generator");
				// if less than support threshold, then this is a rare item generator
				if (sup < this.getMinRareItemsetSupport())
				{
					this.writeToFile(this.bwZG, itemset, sup);
				} else if (sup < this.getMinFreqItemsetSupport())
				{ // if less than support threshold, then this is a rare item generator
					// testing
					// assertNotSubset(entry.getKey(), this.minRareGenerators);
					this.iterationItemsetCount++;
					this.stats.numItemsetItems += itemset.cardinality();
					this.writeToFile(this.bwMRG, itemset, sup);
				} else
				{ // otherwise is a frequent generator
					// this.frequentGenerators.add(entry.getKey());
					currentFrequentGenerators.put(itemset, sup);
				}
			}
		}
		this.stats.numItemsets += this.iterationItemsetCount;
		this.stats.numIterationItemsets.add(this.iterationItemsetCount);
		return currentFrequentGenerators;
	}

	
	private Map<BitSet, Integer> sortGenerators(
							Map<BitSet, Integer> candidates,
							Map<BitSet, Integer> ithLayerItemSetFreqs) {

		this.iterationItemsetCount = 0;
		Map<BitSet, Integer> results = new HashMap<BitSet, Integer>();

		// testing
		assert (candidates.keySet().equals(ithLayerItemSetFreqs.keySet()));

		for (BitSet itemset : candidates.keySet()) {
			int itemsetSupport = ithLayerItemSetFreqs.get(itemset);
			if (itemsetSupport < candidates.get(itemset)) {	// test to determine if generator
				if (itemsetSupport == 0) { // zero generator
					this.iterationItemsetCount++;
					this.stats.numItemsetItems += itemset.cardinality();
					this.writeToFile(this.bwZG, itemset, itemsetSupport);
				} else if (itemsetSupport < this.getMinFreqItemsetSupport()) { // rare generator
					this.iterationItemsetCount++;
					this.stats.numItemsetItems += itemset.cardinality();
					this.writeToFile(this.bwMRG, itemset, itemsetSupport);
				} else { // frequent generator
					results.put(itemset, itemsetSupport);
				}
			}
		}
		this.stats.numItemsets += this.iterationItemsetCount;
		this.stats.numIterationItemsets.add(this.iterationItemsetCount);

		return results;
	}
	
	private void writeToFile(BufferedWriter bw, BitSet itemset, int sup) {
		if (!write)
			return;
		try
		{
			bw.append(itemset + "," + sup);
			bw.newLine();
		} catch (IOException e)
		{
			e.printStackTrace();
		}
	}
	
	@Override
	public void setMinRareItemsetSupport(int minRareItemsetSupport)
	{
//		if (minRareItemsetSupport != 1)
//			throw new IllegalArgumentException("minRareItemsetSupport must always be 1 for MrgExp.");
		super.setMinRareItemsetSupport(minRareItemsetSupport);
		this.stats.minRareItemsetSup = minRareItemsetSupport;
	}

	@Override
	public void setMinFreqItemsetSupport(int minFreqItemsetSupport)
	{
		super.setMinFreqItemsetSupport(minFreqItemsetSupport);
		this.stats.minFreqItemsetSup = minFreqItemsetSupport;
	}
	
}
